#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# ======================================================
# @File:      : test53
# @Author     : forward_huan
# @Date       : 2024/11/17 20:55
# @Desc       :
# ======================================================
from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_sum, cur_sum = nums[0], nums[0]
        for num in nums[1:]:
            if num < 0:
                max_sum = max(max_sum, cur_sum)
            if cur_sum < 0:
                cur_sum = num
            else:
                cur_sum += num
        return max(max_sum, cur_sum)


print(Solution().maxSubArray(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(Solution().maxSubArray(nums=[5, 4, -1, 7, 8]))
print(Solution().maxSubArray(nums=[-1]))
print(Solution().maxSubArray(nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]))
